package 递归;

import java.util.*;

/**
 * @PackageName: 递归
 * @ClassName: LeetCode394
 * @Author: chen jinxu
 * @Date: 2022/8/14 16:41
 * @Description: //字符串解码
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 *
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 */
public class LeetCode394Stack {
    public static void main(String[] args) {
        System.out.println(decodeString("3[a]2[bc]"));
        System.out.println(decodeString("3[a2[c]]"));
        System.out.println(decodeString("2[abc]3[cd]ef"));
        System.out.println(decodeString("abc3[cd]xyz"));
    }
    static int ptr;
    public static String decodeString(String s) {
        LinkedList<String> stack = new LinkedList<>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈(可能为多位，因此使用while循环拼接)
                String digits = getDigits(s);
                stack.addLast(digits);                          
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stack.addLast(String.valueOf(s.charAt(ptr++)));
            } else {
                // 为‘】’   跳到下一位开始出栈
                ++ptr;
                LinkedList<String> sub = new LinkedList<>();
                while (!"[".equals(stack.peekLast())) {
                    sub.addLast(stack.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stack.removeLast();
                // 此时栈顶为sub字符串对应的 数字
                int repTime = Integer.parseInt(stack.removeLast());
                StringBuilder tmp = new StringBuilder();
                String o = getString(sub);
                for (int i = 0; i < repTime; i++) {
                    tmp.append(o);
                }
                // 将构造好的字符串入栈
                stack.addLast(tmp.toString());
            }
        }
        return getString(stack);
    }
    public static String getString(LinkedList<String> v) {
        StringBuilder sb = new StringBuilder();
        for (String s : v) {
            sb.append(s);
        }
        return sb.toString();
    }

    private static String getDigits(String s) {
        StringBuilder sb = new StringBuilder();
        while (Character.isDigit(s.charAt(ptr))) {
            sb.append(s.charAt(ptr++));
        }
        return sb.toString();
    }

}
